package leetcode.all;

import java.util.ArrayList;

public class Solution488 {


    public static void main(String[] args) {
        System.out.println(new Solution488().findMinStep("RRWWRRBBRR","WB"));
//        StringBuilder s = new StringBuilder("wwbbbww");
//        System.out.println(new Solution488().shrink(s));
    }

    int min = 10; //hand.len<=5

    public int findMinStep(String board, String hand) {
        StringBuilder curBoard = new StringBuilder(board);
        char[] handChars = hand.toCharArray();
        for (int i = 0; i < handChars.length; i++) {
            backTrace(curBoard,handChars,i,0);
        }
        return min==10?-1:min;
    }

    public void backTrace(StringBuilder curBoard, char[] handChars, int curIdx, int total){

        //不符合条件情况1：当前字符已经使用
        if(handChars[curIdx]=='0') return;
        char curChar = handChars[curIdx];

        //不符合条件情况2：当前字符未在curBoard出现
        boolean flag = true;
        ArrayList<Integer> idxes = new ArrayList<>();
        int i = -1;
        String curString = String.valueOf(curChar);
        while ((i=curBoard.indexOf(curString,i+1))!=-1) idxes.add(i);
        //如果当前字符没用，退出
        if(idxes.isEmpty()) return;

        //尝试将字符插入idxes中位置
        total++;
        handChars[curIdx] = '0';
        for (Integer idx : idxes) {
            StringBuilder tmp = new StringBuilder(curBoard).insert(idx,curString);
            if(shrink(tmp).length()==0){
                min = Math.min(total,min);
                break;
            }else {
                //插入此位置不能完全消除，进入递归
                for (int j = 0; j < handChars.length; j++) {
                    backTrace(tmp,handChars,j,total);
                }
            }
        }
        total--;
        handChars[curIdx] = curChar;
    }

    /**
     * 把三个或以上连着的删去
     * @param s
     * @return
     */
    public StringBuilder shrink(StringBuilder s){
        if(s.length()==0) return s;

        ArrayList<int[]> deleteSeg = new ArrayList<>();//记录要删除的段,[末尾,段长]
        char c = s.charAt(0);
        int len = 1;
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i)==c) len++;
            else{
                if(len>=3)  deleteSeg.add(new int[]{i,len});
                c = s.charAt(i);
                len = 1;
            }
        }
        //最终结束时可能没删末尾
        if(len>=3) deleteSeg.add(new int[]{s.length(),len});
        //递归出口，s不能继续shrink了
        if(deleteSeg.isEmpty()) return s;
        //真正开始删除
        int accum = 0; //已删除的段长
        for (int[] ints : deleteSeg) {
            int end = ints[0], segLen = ints[1];
            s.delete(end-segLen-accum,end-accum);
            accum += segLen;
        }
        return shrink(s);
    }

}
